package org.example.l0;

import org.junit.jupiter.api.Test;

import java.util.stream.LongStream;

public class divide {

    @Test
    void run() {
        int divide = divide(-2147483648, -1);
        System.out.println(divide);
    }

    public int divide(int dividend,
                      int divisor) {
        // 考虑被除数为最小值的情况
        if (dividend == Integer.MIN_VALUE) {
            if (divisor == 1) {
                return Integer.MIN_VALUE;
            }
            if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
        }
        // 考虑除数为最小值的情况
        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }

        boolean revert = true;
        if (dividend > 0) {
            dividend = -dividend;
            revert = !revert;
        }

        if (divisor > 0) {
            divisor = -divisor;
            revert = !revert;
        }

        int i = dividend, j = 0;

        int ans = 0;
        out:
        while (i <= j) {
            int mid = j + ((i - j) >> 1);
            State state = gt(dividend, divisor, mid);
            switch (state) {
                case EQ:
                    ans = mid;
                    break out;
                case LT:
                    if (mid == Integer.MIN_VALUE) {
                        break out;
                    }
                    j = mid - 1;
                    break;
                default:
                    ans = mid;
                    i = mid + 1;
            }
        }

        if (ans == Integer.MIN_VALUE && revert) {
            return Integer.MAX_VALUE;
        }

        return revert ? -1 * ans : ans;
    }

    enum State {
        EQ, GT, LT,
    }

    State gt(int dividend,
             int divisor,
             int mid) {
        long sum = 0;
        int z = Math.abs(Math.max(mid, divisor));
        int add = Math.min(mid, divisor);
        for (; z != 0; z >>= 1) {
            if ((z & 1) == 1) {
                sum += add;
                if (sum < dividend) {
                    return State.GT;
                }
            }

            if (z != 1) {
                add += add;
            }
        }

        if (sum == dividend) {
            return State.EQ;
        }
        return State.LT;
    }

    @Test
    void add() {
        System.out.println(add(5, 100));
    }

    long add(int a,
             int b) {
        int ans = 0;
        for (; b != 0; b >>= 1) {
            if ((b & 1) == 1) {
                ans += a;
            }
            a += a;
        }
        return ans;
    }

    public int divideV3(int dividend,
                      int divisor) {
        if (divisor == 1) {
            return dividend;
        }

        if (Math.abs(dividend + 0l) < Math.abs(divisor + 0l)) {
            return 0;
        }

        int i = Math.min(dividend, 0), j = Math.max(dividend, 0);
        int cnt = Math.abs(divisor);
        int sign = divisor > 0 ? 1 : -1;

        for (; i <= j; ) {
            long mid = (0L + i + j) >> 1;
            long sum = LongStream.range(0, cnt).map(e -> mid).sum();
            if (sum == dividend) {
                i = j = Math.toIntExact(mid);
                break;
            }

            if (sum > dividend) {
                j = (int) (mid - 1l);
            } else {
                i = (int) (mid + 1l);
            }
        }


        long res = 1l * (dividend < 0 ? i : j) * sign;
        if (res >= Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }

        if (res <= Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }

        return (int) res;
    }
}
